#include <iostream>
using namespace std;
int ans[1000010];
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= 1000000; ++i)
        if (i <= 2)
            ans[i] = i;
        else
            ans[i] = (2 * ans[i - 1] + ans[i - 2]) % 32767;
    while (n--){
        int num;
        cin >> num;
        cout << ans[num] << " ";
    }
    return 0;
}